﻿#define _CRT_SECURE_NO_WARNINGS 1
// 动态规划

//class Solution
//{
//public:
//    int calculateMinimumHP(vector<vector<int>>& dungeon) {
//        int m = dungeon.size();
//        int n = dungeon[0].size();
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
//        // 初始化--因为有未知数值
//        dp[m][n - 1] = dp[m - 1][n] = 1;
//        // 循环递推
//        for (int i = m - 1; i >= 0; i--)
//        {
//            for (int j = n - 1; j >= 0; j--)
//            {
//                dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j], 1);
//            }
//        }
//        // 结果
//        return dp[0][0];
//    }
//};

//#include <algorithm>
//class Solution {
//public:
//    int MaxData(vector<int>& dp, int x)
//    {
//        int maxdata = dp[x];
//        for (int i = x; i >= 1; i--)
//        {
//            maxdata = max(maxdata, dp[i]);
//        }
//        return maxdata;
//    }
//    int massage(vector<int>& nums) {
//        if (nums.empty()) return 0;
//        vector<int> dp(nums.size() + 1);
//        // 初始化
//        dp[1] = nums[0];
//        // 计算
//        for (int i = 2; i <= nums.size(); i++)
//        {
//            dp[i] = nums[i - 1] + MaxData(dp, i - 2);
//        }
//
//        sort(dp.begin(), dp.end(), greater<int>());
//
//        return dp[0];
//    }
//};

//class Solution {
//public:
//    int rob(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> dp(n + 1);
//        dp[1] = nums[0];
//        for (int i = 2; i < n; i++)
//        {
//            int maxdata = dp[i - 2];
//            if (i > 2) maxdata = max(maxdata, dp[i - 3]);
//            dp[i] = nums[i - 1] + maxdata;
//        }
//
//        int maxdata = 0;
//        for (int i = 2; i < n - 1; i++)
//        {
//            maxdata = max(maxdata, dp[i]);
//        }
//        dp[n] = nums[n - 1] + maxdata;
//        sort(dp.begin(), dp.end(), greater<int>());
//        return dp[0];
//    }
//};

//class Solution {
//public:
//    int rob(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 1) return nums.front();
//        if (n == 2) return nums[0] > nums[1] ? nums[0] : nums[1];
//        return max(Table(nums, 0, n - 2), Table(nums, 1, n - 1));
//    }
//    int Table(vector<int>& nums, int left, int right)
//    {
//        vector<int> dp(right - left + 1);
//        dp[0] = nums[left];
//        dp[1] = nums[left + 1];
//        int n = 2;
//        int maxdata = 0;
//        for (int i = left + 2; i <= right; i++)
//        {
//            maxdata = max(maxdata, dp[n - 2]);
//            dp[n++] = nums[i] + maxdata;
//        }
//        sort(dp.begin(), dp.end(), greater<int>());
//        return dp[0];
//    }
//};

//class Solution {
//public:
//    bool CheckSame(vector<int>& nums)
//    {
//        auto it = nums.begin() + 1;
//        auto its = nums.begin();
//        while (it != nums.end())
//        {
//            int data = *its;
//            while (it != nums.end() && *it == data)
//            {
//                *its += data;
//                it = nums.erase(it);
//            }
//            if (it == nums.end()) break;
//            its = it;
//            it++;
//        }
//        sort(nums.begin(), nums.end(), greater<int>());
//
//        int x = nums[0];
//        for (int i = 1; i < nums.size(); i++)
//        {
//            if (x == nums[i]) true;
//            x = nums[i];
//        }
//        return false;
//    }
//    int deleteAndEarn(vector<int>& nums) {
//        sort(nums.begin(), nums.end());
//
//        while (CheckSame(nums)) {}
//
//        int value = 0;
//        for (int i = 0; i < nums.size(); i += 2)
//        {
//            value += nums[i];
//        }
//        return value;
//    }
//};

//class Solution {
//public:
//    int deleteAndEarn(vector<int>& nums) {
//        // 转换为打家劫舍问题
//        sort(nums.begin(), nums.end(), greater<int>());
//        vector<int> arr(nums[0] + 1);
//        for (auto& e : nums) arr[e] += e;
//
//        int n = arr.size();
//        vector<int> dp(n);
//        dp[1] = arr[1];
//        int maxdata = 0;
//        for (int i = 2; i < n; i++)
//        {
//            maxdata = max(maxdata, dp[i - 2]);
//            dp[i] = arr[i] + maxdata;
//        }
//        sort(dp.begin(), dp.end(), greater<int>());
//        return dp[0];
//    }
//};

//class Solution {
//public:
//    int MinData(vector<vector<int>>& dp, int x, int y)
//    {
//        int mindata = INT_MAX;
//        for (int j = 0; j < 3; j++)
//        {
//            if (j != y) mindata = min(dp[x - 1][j], mindata);
//        }
//        return mindata;
//    }
//    int minCost(vector<vector<int>>& costs) {
//        int n = costs.size();
//        vector<vector<int>> dp(n, vector<int>(3));
//        dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2];
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = 0; j < 3; j++)
//            {
//                dp[i][j] = costs[i][j] + MinData(dp, i, j);
//            }
//        }
//        return min(min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
//    }
//};

